Resource allocation systems, such as may be found in computer systems, call centers, contact centers, automated business process systems and other systems that provide resources for performing tasks require that such tasks be scheduled. As the number of tasks scheduled for completion by a resource allocation system increases, the accompanying growth in the number of scheduled tasks becomes an increasing burden on the resource allocation system. This burden is exacerbated by algorithms in which a significant number of scheduled tasks are canceled and rescheduled.
In general, the cost of canceling a task is minimal. However, the cost of reinserting a rescheduled task into a scheduling queue becomes exorbitant where a large number of scheduled tasks are maintained by a scheduler. In order to provide for simple insertion of a newly received or rescheduled task, an array based scheduler may be used. In an array based scheduler, a list of timers is maintained, in which each timer relates to the time for performance of a scheduled task. When a task is inserted into an array based scheduler, it may simply be appended to the list of timers already included in the array. Cancellation of a scheduled task from an array based scheduler simply requires deletion of the timer associated with the canceled task. However, each item in an array based scheduler must typically be scanned in order to locate the next timer to expire, and thus the next task to be performed.
In order to simplify identifying a next task to be performed, a delta queue based scheduler may be used. In a delta queue based scheduler, scheduled items are maintained in time order. In particular, the delta between succeeding items in the queue are calculated and maintained. Accordingly, by referencing the delta, the time to the next scheduled event is apparent. However, when a new or reinserted item is placed in a delta queue, a significant portion of the delta queue must be scanned in order to find the proper insertion point for the item. In addition, the delta between the newly inserted item and the preceding item must be calculated, as must the delta between the newly inserted item and any succeeding items.
Accordingly, while scheduling arrays require few processing resources in connection with adding new tasks or canceling previously scheduled tasks, they are relatively processor resource intensive in connection with identifying a next task for delivery to a resource. Conversely, while a delta queue scheduler is relative processor resource intensive in connection with the addition of a new task or cancellation of a scheduled task, delta queue schedulers require relatively few processor resources in connection with identifying a next task for delivery to a resource. Accordingly, designers of resource allocation systems have been required to choose from either an array based scheduler or a delta based scheduler based on a prediction as to which type of scheduler would provide the greatest efficiency in connection with a particular resource allocation system.